Many modern communications systems are “secure.” A secure system is one that gives communications privileges to authorized users and denies communications privileges to unauthorized users. Some such systems accomplish security by employing “encryption keys.” Encryption keys are also known as “authentication keys,” “authentication certificates” or simply “keys.” Keys are distributed to communications nodes within the system. Authorized users, during secure communications sessions, access the nodes, and encrypt and decrypt messages using the keys.
Security can become compromised when an unauthorized user gains access to a node that has a valid key. When this occurs, the node accessed by the unauthorized user is considered compromised. The unauthorized user of a compromised node can decrypt (and steal) messages and can also be disruptive to the system by encrypting and sending unauthorized messages. Examples of disruption include gaining access to the system without paying fees, or gaining access to classified material. Examples of unauthorized users include “hackers” who break into a system and thieves who physically take possession of a system node with a valid key. Specific examples include people who steal television service by cracking the video encryption key, and cellular service thieves who capture authentication codes and then replicate phones.
After the system becomes compromised, system security can be regained by “excising” the compromised node from the communications system. Nodes can be excised by “re-keying” all nodes except the compromised node. For example, when one compromised node exists in a system that includes ten nodes, the compromised node can be excised by sending the remaining nine nodes a new encryption key using nine separate messages.
When large numbers of nodes exist, sending a new key to each node is expensive in terms of time and bandwidth. For example, when one compromised node exists in a system having 10,000 total nodes, re-keying the remaining nodes is accomplished by sending 9,999 messages. This can consume considerable system resources. As the communications system grows larger, excising a compromised node becomes even more expensive.
Accordingly, a significant need exists for methods and apparatus for efficiently re-keying large numbers of nodes in communications systems.